1. Field of the Invention
The invention is related generally to multiprocessing computer systems and more particularly to the selection of one of a plurality of processors to communicate on a common communications bus.
2. Background Art
Multiprocessing techniques have become widely used in computing systems. Essentially, multiprocessing systems employ a plurality of processing devices operating substantially independent from one another to thereby enable the computing system to simultaneously accomplish a variety of different tasks.
Rather than provide each of the processors with a complete independent computing system having inputs, processing, and storage along with outputs, a plurality of processors are interconnected by a single communications bus.
In computer systems, design tradeoffs in circuit packaging, technology, cost and system performance often result in the implementation of shared buses for the transfer of information such as data, commands or other messages. In systems that utilize high speed parallel buses which interconnect several devices of similar function and bus priority, it is necessary that each device be given sufficient allocation in bus access to balance bus utilization, i.e., bandwidth. For optimum operation, it is also necessary that the average wait time for all devices in accessing the bus be as small as possible. It is further necessary for optimum performance that the arbitration mechanism which determines priority in access to the shared bus be as fast as possible, particularly in terms of logic level transitions, to calculate the next device grant.
Prior art techniques for selecting the processor for access to the bus have generally involved the use of discrete combinatorial and sequential logic elements and have therefore been highly complex and cumbersome in use. Further, such prior art techniques are relatively inflexible in operation, thus limiting the ability of such systems to accommodate for particular contingencies. For example, in many systems, the routine priority scheme may be upset by special memory requests, such as a multi-cycle request where the requesting processor requires a memory access involving more than a single memory cycle. Other special priority requests include "super priority" requests such as memory refresh cycles which must be performed to the exclusion of all other memory accesses. The prior art techniques employing discrete components cannot easily accommodate such non-routine memory requests without involving highly complex circuitry.
Conventional bus arbitration schemes generally implement a fixed, unchanging priority scheme among the using devices. Non programmable hardware logic generates bus use grant signals as a function of the incoming request signals in a fixed and unchanging priority structure. Such schemes are inflexible because the priority structure is built into the logic hardware and there is no way, short of redesigning the arbitration circuit, to accommodate different applications or changing system configurations and request loads.
The prior art has sought to alleviate these limitations by providing programmable arbitration mechanisms in which the relative priority ordering of the using devices is indicated by the contents of storage devices, such as registers, and hence may be changed by reprogramming the register contents.
While providing programmability at one level, these mechanisms have not met the needs of multiprocessor computer systems and other bus-oriented digital systems that require flexible, programmable, class-oriented priority schemes. In such systems, using devices are commonly divided into classes, with each class having a different priority, while devices within a class have the same priority and are generally scheduled to access the bus in a round-robin, equal opportunity, manner. The prior art programmable arbitration mechanisms have traditionally not possessed the flexibility necessary to adapt to such a variety and combination of priority determining manners. Hence the prior art mechanisms have not been capable of meeting the changing needs of a variety of arbitrator applications, configurations of using devices and device response time requirements.
Typical multiprocessor environments employ a common backplane bus to connect a plurality of processors. To interrupt a central processor each device must send an interrupt signal to the processor. Due to packaging constraints dedicated interrupt lines are at a premium. Many interrupt schemes have been implemented in the past to control the accessing of data in a computerized system. Fixed, as well as programmable, priority interrupt systems are available. As data acquisition rates increase with faster processors and the emergence of 32-bit processors, faster priority interrupt schemes are needed. To save dedicated interrupt lines and the associated integrated circuit pinouts, what is needed is a bus interrupt technique that uses the backplane bus. A device desiring access to the bus interrupts by first broadcasting its priority onto the bus and then sending an interrupt message.
Also common in the prior art in a centralized arbitration scheme, where a central arbitrator determines which module will receive the bus use next. This is the conventional way and has the disadvantage of a single point of failure (that is, when the centralized arbitrator fails, everything stops). This is unacceptable in fault tolerance systems, like space projects, banking, and critical industrial processes which can not use a centralized arbitration scheme.
What is needed is a distributed programmable priority scheme to solve the problems encountered in the prior art.